#include<iostream>
#include<utility>
#include<vector>
#include<time.h>
using namespace std;

enum Colour {
    RED,
    BLACK
};

template<class K , class V>
class RBTreeNode {
public:
    //构造函数
    RBTreeNode(const pair<K,V>& kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_kv(kv)
    ,_col(RED)
    {}

    //成员变量
    RBTreeNode<K,V>* _left;
    RBTreeNode<K,V>* _right;
    RBTreeNode<K,V>* _parent;
    pair<K,V> _kv;
    Colour _col;
};

template<class K , class V>
class RBTree {
    typedef RBTreeNode<K,V> Node;
public:
    //构造函数
    RBTree()
    :_root(nullptr)
    {}

    bool insert(const pair<K,V>& kv) {
        if(_root==nullptr){
            _root=new Node(kv);
            _root->_col=BLACK;
            return true;
        }

        Node* parent=nullptr;
        Node* cur=_root;

        while(cur) {
            if(cur->_kv.first<kv.first) {
                parent=cur;
                cur=cur->_right;
            }
            else if(cur->_kv.first>kv.first) {
                parent=cur;
                cur=cur->_left;
            }
            else {
                return false;
            }
        }

        cur=new Node(kv);
        cur->_col=RED;

        if(parent->_kv.first<kv.first){
            parent->_right=cur;
        }
        else{
            parent->_left=cur;
        }
        cur->_parent=parent;

        while(parent&&parent->_col==RED){
            Node* grandfather=parent->_parent;

            //如果parent节点在左子节点
            if(parent==grandfather->_left){
                Node* uncle=grandfather->_right;
                //如果uncle节点存在且节点为红色
                if(uncle&&uncle->_col==RED){
                    //变色
                    parent->_col=uncle->_col=BLACK;
                    grandfather->_col=RED;

                    //继续往上
                    cur=grandfather;
                    parent=cur->_parent;
                }

                //如果uncle节点不存在 或者 节点为黑色
                else{
                    //如果cur节点在左子节点
                    if(cur==parent->_left){
                        //右单旋
                        RotateR(grandfather);

                        //旋转后变色
                        grandfather->_col=RED;
                        parent->_col=BLACK;
                    }

                    //如果cur节点在右子节点
                    else{
                        //左双旋
                        //先左单旋，再右单旋
                        RotateL(parent);
                        RotateR(grandfather);

                        //旋转后变色
                        cur->_col=BLACK;
                        grandfather->_col=RED;
                    }
                    break;
                }
            }

            //如果parent节点在右子节点
            else{
                Node* uncle=grandfather->_left;

                //如果uncle节点存在且节点为红色
                if(uncle&&uncle->_col==RED){
                    //变色
                    parent->_col=uncle->_col=BLACK;
                    grandfather->_col=RED;

                    //继续往上
                    cur=grandfather;
                    parent=cur->_parent;
                }

                //如果uncle节点不存在 后者 节点为黑色
                else{
                    //如果cur节点在右子节点
                    if(cur==parent->_right){
                        //左单旋
                        RotateL(grandfather);

                        //变色
                        parent->_col=BLACK;
                        grandfather->_col=RED;
                    }

                    //如果cur节点在左子节点
                    else{
                        //右双旋
                        //先右单旋，再左单旋
                        RotateR(parent);
                        RotateL(grandfather);

                        //旋转后变色
                        cur->_col=BLACK;
                        grandfather->_col=RED;
                    }
                    break;
                }
            }
        }
        _root->_col=BLACK;

        return true;
    }

    int Height(){
        return _Height(_root);
    }

    bool IsBlance(){
        return _IsBlance(_root);
    }


private:
    int _Height(Node* root){
        if(root==nullptr){
            return 0;
        }

        int leftheight=_Height(root->_left);
        int rightheight=_Height(root->_right);

        return leftheight>rightheight ? leftheight+1 : rightheight+1;
    }

    bool CheckColour(Node* root,int blacknum,int benchmark){
        //如果节点是空，判断黑色节点个数是否等于基准值
        if(root==nullptr){
            if(blacknum!=benchmark){
                return false;
            }
            return true;
        }

        //如果节点是黑色，黑色个数加加
        if(root->_col==BLACK){
            blacknum++;
        }

        //如果节点是红色，判断父节点是否也是红色，不能出现连续的红色节点
        if(root->_col==RED&&root->_parent&&root->_parent->_col==RED){
            cout<<root->_kv.first<<"RED False"<<endl;
            return false;
        }

        return CheckColour(root->_left,blacknum,benchmark)
               &&CheckColour(root->_right,blacknum,benchmark);
    }

    bool _IsBlance(Node* root){
        if(root==nullptr){
            return true;
        }

        //如果根节点不是黑色，返回错误
        if(root->_col!=BLACK){
            return false;
        }

        //设置一个基准值
        int benchmark=0;
        Node* cur=root;
        while(cur){
            if(cur->_col==BLACK){
                benchmark++;
            }
            cur=cur->_left;
        }

        return CheckColour(root,0,benchmark);
    }


    //左单旋
    void RotateL(Node* parent){
        Node* cur=parent->_right;
        Node* curleft=cur->_left;
        Node* ppnode=parent->_parent;

        parent->_right=curleft;
        if(curleft){
            curleft->_parent=parent;
        }

        cur->_left=parent;
        parent->_parent=cur;

        if(ppnode){
            if(ppnode->_left==parent){
                ppnode->_left=cur;
                cur->_parent=ppnode;
            }
            else{
                ppnode->_right=cur;
                cur->_parent=ppnode;
            }
        }
        else{
            cur->_parent=nullptr;
            _root=cur;
        }
    }

    //右单旋
    void RotateR(Node* parent){
        Node* cur=parent->_left;
        Node* curright=cur->_right;
        Node* ppnode=parent->_parent;

        parent->_left=curright;
        if(curright){
            curright->_parent=parent;
        }

        cur->_right=parent;
        parent->_parent=cur;

        if(ppnode){
            if(ppnode->_left==parent){
                ppnode->_left=cur;
                cur->_parent=ppnode;
            }
            else{
                ppnode->_right=cur;
                cur->_parent=ppnode;
            }
        }
        else{
            cur->_parent=nullptr;
            _root=cur;
        }
    }

private:
    Node* _root;
};